package com.zto.sch.advance.algorithms.algorithms4;

import org.junit.Test;

/**
 * @program: sch-diy-parent
 * @description:
 * @author: sch
 * @create: 2021-07-19 10:45
 **/
public class 最大公约数最小公倍数 {
    public static void main(String[] args) {
        int a = 270, b = 192;
        int abDivsor = getTwoNumCommonDivsor(a, b);
        int abMultiple = getTwoNumCommpnMultiple(a, b);
        System.out.println(a + ",和" + b + "的最大公约数是:" + abDivsor + ";最小公倍数是:" + abMultiple);
    }

    /**
     * 最大公约数 欧几里得算法
     * 思路：
     * a%b = temp
     * b%temp = ？
     * 依次类推 r是最终的最大公约数
     * <p>
     * 实现过程：
     * 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数
     * 1、大数放a中、小数放b中；
     * 2、求a/b的余数；
     * 3、若temp=0则b为最大公约数；
     * 4、如果temp!=0则把b的值给a、temp的值给a；
     * 5、返回第二步；
     *
     * @param a
     * @param b
     * @return
     */
    private static int getTwoNumCommonDivsor(int a, int b) {
        if (a <= 0 || b <= 0) {
            throw new RuntimeException("数据有误");
        }
        int max = Math.max(a, b);
        int min = Math.min(a, b);

        int temp = max % min;
        if (temp == 0) {
            return min;
        }

        return getTwoNumCommonDivsor(b, temp);
    }


    /**
     * 最小公倍数：a*b/temp
     *
     * @return
     */
    public static int getTwoNumCommpnMultiple(int a, int b) {
        if (a <= 0 || b <= 0) {
            throw new RuntimeException("数据有误");
        }
        int twoNumCommonDivsor = getTwoNumCommonDivsor(a, b);

        return (a * b) / twoNumCommonDivsor;
    }


    /**
     * 最大公约数    --  方法二
     *
     * @param a
     * @param b
     * @return
     */
    private static int getTwoNumCommonDivsor2(int a, int b) {
        if (a <= 0 || b <= 0) {
            throw new RuntimeException("数据有误");
        }
        if (b > a) {
            int t = a;
            a = b;
            b = t;
        }

        int temp = a % b;
        while (temp != 0) {
            a = b;
            b = temp;
            temp = a % b;
        }

        return b;
    }

    @Test
    public void test() {
        int twoNumCommpnMultiple = getTwoNumCommonDivsor2(7, 14);
        System.out.println(twoNumCommpnMultiple);
    }


}
